package leetcode.datastructure.array;

import java.util.Arrays;

public class Program189ArrayRotate {
    public Program189ArrayRotate() {
    }

    public void rotate(int[] nums, int k) {

//        pointTrance(nums, k);
        segement(nums, k);
    }

    /**
     * 从0开始，追踪下去，记录要替换的值、以及后续替换计算位置
     * @param nums
     * @param k
     */
    public void pointTrance(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 数组翻转
     * 关键找到可以本地替换的准确位置
     * 不要考虑移动
     * @param nums
     * @param k
     */
    public void segement(int[] nums, int k) {
        int length = nums.length;
        if (length == 1) {
            return;
        }
        k = k % length;
        // 空间复杂度O(1)

        reverse(nums, 0, length - 1);
        reverse(nums, 0, k -1);
        reverse(nums, k, length - 1);

    }



    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        Program189ArrayRotate myStack = new Program189ArrayRotate();
        int[] nums3 = {1,2,3,4,5,6,7};
        myStack.rotate(nums3, 3);
        System.out.println(nums3[0]); // 返回
    }
}
